/*
 * This project provides a number of implementations for indexing and evaluating
 * <i>Continuous Top-k Queries over Text Streams</i>
 * and has been developped as part of the work described in the article:
 * 
 * Vouzoukidou, N., Amann, B., & Christophides, V. (2012, October). 
 * Processing continuous text queries featuring non-homogeneous scoring functions.
 * In Proceedings of the 21st ACM international conference on Information and 
 * knowledge management (pp. 1065-1074). ACM.
 * http://dl.acm.org/citation.cfm?id=2398404
 * 
 * This software is distributed under the GNU General Public License and as an
 * additional condition of usage, please cite the aforementioned article.
 * 
 * Copyright (C) 2012 ICS/FORTH, Greece and 
 *               2012 LIP6, France
 * 
 * Author: Vouzoukidou Nelly, email: nelly.vouzoukidou (at) gmail (dot) com
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */
package gr.forth.ics.continuoustopk.index;

import gr.forth.ics.continuoustopk.Item;
import gr.forth.ics.continuoustopk.Constants;
import gr.forth.ics.continuoustopk.Query;
import gr.forth.ics.continuoustopk.Term;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * @author Vouzoukidou Nelly, email: nelly.vouzoukidou (at) gmail (dot) com
 */
public class ColFilterQueryIndex extends AbstractQueryIndex {
    private Map<Term, Map<Query, Query>> map;

    ColFilterQueryIndex() {
        map = new HashMap<Term, Map<Query, Query>>();
    }

    private static Comparator<Query> comparator(final Term term) {
        return new Comparator<Query>() {
            public int compare(Query q1, Query q2) {
                if (q1 == q2) {
                    return 0;
                }
                double w1 = q1.getWeight(term) / q1.minScore();
                double w2 = q2.getWeight(term) / q2.minScore();

                if (w1 < w2) {
                    return 1;
                } else if (w1 > w2) {
                    return -1;
                }
                // equal weights: giving some random ordering (otherwise the two
                // queries would be considered equal by the treemap and one of
                // them would be ignored
                if (q1.hashCode() == q2.hashCode()) {
                    if (!q1.equals(q2)) {
//                        System.err.println("ERROR in hashCode of queries (" + q1.hashCode() + ")" + q1 + ", " + q2);
                        return q1.toString().compareTo(q2.toString());
                    }
                }
                return q1.hashCode() > q2.hashCode() ? 1 : -1;
            }
        };
    }

    public void add(Query query) {
        for (Term term : query) {
            Map<Query, Query> termSet = map.get(term);
            if (termSet == null) {
                termSet = new TreeMap<Query, Query>(comparator(term));
                map.put(term, termSet);
            }
            termSet.put(query, query);
        }
    }

    // <editor-fold defaultstate="collapsed" desc="secondary methods for matching">
    private void checkItem(Item item) {
        // this index only supports item score equal to 0
        if (Constants.alpha != 0 && item.itemScore() != 0) {
            throw new UnsupportedOperationException("Found item score or alpha different from 0: " + item + ", " + Constants.alpha);
        }
    }
    private void createToProcessLists(Item item, List<Iterator<Query>> toProcess, List<Term> toProcessTerms) {
        for (Term term : item) {
            Map<Query, Query> termSet = map.get(term);
            if (termSet == null) {
                continue;
            }
            toProcess.add(termSet.keySet().iterator());
            toProcessTerms.add(term);
        }
    }
    private void delete(Query query) {
        for (int i = 0; i < query.termCount(); i++) {
            map.get(query.getTerm(i)).remove(query);
        }
    }
    private void updateQueries(Set<Query> toUpdate, Item item) {
        if (updateStrategy == UpdateStrategy.doNothing) {
            return;
        }
        for (Query query : toUpdate) {
            delete(query);
            double score = Constants.rankingFunction.score(query, item);
            updateStrategy.maybeUpdate(query, item, score);
            for (int i = 0; i < query.termCount(); i++) {
                map.get(query.getTerm(i)).put(query, query);
            }
        }
    }
    private void checkOrder(Term term) {
        Map<Query, Query> list = map.get(term);
        Comparator<Query> comp = comparator(term);
        Query previous = null;
        for (Query key : list.keySet()) {
            if (previous == null) {
                previous = key;
                continue;
            }

            if (comp.compare(previous, key) >= 0) {
                System.err.println("Reverse order: " + previous + " - " + key);
                comp.compare(previous, key);
            }
            previous = key;
        }
    }
    // debugging code
    private void checkOrder(Item item) {
        for (Term term : item) {
            checkOrder(term);
        }
    }
    // </editor-fold>

    protected void matchItem(Item item) {
        checkItem(item);

        List<Iterator<Query>> toProcess = new LinkedList<Iterator<Query>>();
        List<Term> toProcessTerms = new LinkedList<Term>();
        createToProcessLists(item, toProcess, toProcessTerms);

        double[] currPassValues = new double[item.termCount()];
        TopValues topValues = new TopValues();
        Set<Query> toUpdate = new HashSet<Query>();
        
        // while the list is not empty
        while (!toProcess.isEmpty()) {
            Iterator<Term> termsIterator = toProcessTerms.iterator();
            Iterator<Iterator<Query>> toProcessIterator = toProcess.iterator();
            int index = 0;
            // go through the terms
            while (toProcessIterator.hasNext()) {
                Iterator<Query> list = toProcessIterator.next();
                Term term = termsIterator.next();
                Query query = list.next();
                double score = Constants.rankingFunction.score(query, item);
                // if should update: to update add query
                if (shouldUpdate(query, score)) {
                    if (toUpdate.add(query)) {
                        notifyUpdatedListeners(query, item, term, 0);
                    }
                }
                notifyVisitedListeners(query, item, term, 0);
                // evaluate the top-(maxQueryLength)
                double value = query.getWeight(term) * item.getWeight(term) / query.minScore();
                currPassValues[index++] = value;
                topValues.add(value);
            }
            // stopping condition
            index = 0;
            termsIterator = toProcessTerms.iterator();
            toProcessIterator = toProcess.iterator();
            while (toProcessIterator.hasNext()) {
                termsIterator.next();
                if (!toProcessIterator.next().hasNext() || // if the the list is empty
                        topValues.sum + currPassValues[index++] < 1) { // if the sum of top values doesn't reach 1
                    toProcessIterator.remove();
                    termsIterator.remove();
                }
            }
            topValues.clear();
        }
        // handle the toUpdate list
        updateQueries(toUpdate, item);
    }

    public Iterable<Query> queries(Term term) {
        return map.get(term).keySet();
    }

    public void clear() {
        map.clear();
    }

    public Iterator<Term> terms() {
        return map.keySet().iterator();
    }

    public int queryCount(Term term) {
        Map<Query, Query> list = map.get(term);
        if (list == null) return 0;
        return list.size();
    }


    // <editor-fold defaultstate="collapsed" desc="TopValues">
    // for small values of Constant.maxQuerySize this implementation is much
    //      faster than the logn one (with Binary Trees)
    private static class TopValues {
        private double[] values = new double[Constants.maxQuerySize - 1];
        private double sum = 0;

        void add(double value) {
            if (value <= values[values.length - 1]) {
                return;
            }
            // the last value will be removed, subtract it from the sum
            sum += value - values[values.length - 1];
            int i;
            for (i = values.length - 2; i >= 0; i--) {
                if (value <= values[i]) {
                    break;
                }
                values[i + 1] = values[i];
            }
            values[i + 1] = value;
        }

        double sum() {
            return sum;
        }

        void clear() {
            for (int i = 0; i < values.length; i++) {
                values[i] = 0;
            }
            sum = 0;
        }
    }
    // </editor-fold>
}
